W1. Truth Tables, Normal Forms (DNF, CNF)

Author

Zakhar Podyakov

Published

September 17, 2025

Quiz | Flashcards

1. Summary

1.1 Propositions and Logical Values

In logic, a proposition is a statement that can be definitively determined as either True or False, but not both. It is the fundamental building block of logical expressions. For example, “The sky is blue” is a proposition. “What time is it?” is not, because it’s a question and cannot be assigned a truth value. In discrete mathematics and computing, we represent these values numerically:

  • True is represented by 1.
  • False is represented by 0.
1.2 Logical Operators

Logical operators are symbols used to connect propositions and form more complex logical expressions. Each operator has a specific rule for determining the truth value of the expression it forms.

1.2.1 Negation (NOT)

The Negation operator, denoted by \(¬\) (e.g., \(¬P\)), inverts the truth value of a proposition. If \(P\) is true, \(¬P\) is false. If \(P\) is false, \(¬P\) is true. It corresponds to the word “not”.

1.2.2 Conjunction (AND)

The Conjunction operator, denoted by \(&\) or \(∧\) (e.g., \(P ∧ Q\)), connects two propositions. The result is True only if both propositions are true. If either or both are false, the result is false. It corresponds to the word “and”.

1.2.3 Disjunction (OR)

The Disjunction operator, denoted by \(∨\) (e.g., \(P ∨ Q\)), connects two propositions. The result is True if at least one of the propositions is true. It is only false when both propositions are false. This is also known as an inclusive OR.

1.2.4 Implication (IF…THEN)

The Implication operator, denoted by \(→\) (e.g., \(P → Q\)), represents a conditional statement. It is read as “if P, then Q”. The expression \(P → Q\) is only False when \(P\) is true and \(Q\) is false. In all other cases, it is true. This can seem counter-intuitive. Think of it as a promise: “If I pass the exam (\(P\)), then I will celebrate (\(Q\))”. The only way the promise is broken is if I pass the exam but do not celebrate. If I don’t pass the exam, the promise is not broken, regardless of whether I celebrate or not.

1.2.5 Equivalence (IF AND ONLY IF)

The Equivalence operator, denoted by \(↔\) (e.g., \(P ↔ Q\)), is also known as a biconditional. The result is True only when both propositions have the same truth value (both true or both false).

1.3 Truth Tables

A truth table is a tool used to systematically determine the truth value of a complex logical formula for every possible combination of truth values of its component propositions.

  • Construction: To build a truth table for a formula with \(n\) distinct propositional variables, you need \(2^n\) rows to cover all possible scenarios.
  • Structure: The initial columns list all combinations of truth values for the variables. Subsequent columns break down the complex formula into smaller parts, building up to the final result in the last column.
1.4 Normal Forms

A normal form in logic is a standardized way of writing a logical formula. Having a standard representation is useful for comparing formulas, simplifying them, and for automated processing in computer science. The two most common are Disjunctive Normal Form (DNF) and Conjunctive Normal Form (CNF).

1.4.1 Disjunctive Normal Form (DNF)

A formula is in Disjunctive Normal Form (DNF) if it is a disjunction (ORs) of conjuncts (ANDs of literals). A literal is a variable or its negation.

  • Structure: \((A \land \neg B) \lor (C \land D) \lor (\neg E)\)
  • Intuition: Think of DNF as describing the specific conditions that make the formula True. Each conjunct represents one “true” scenario. The entire formula is true if any one of these scenarios is met.
Algorithm to Find DNF from a Truth Table:
  1. Identify all rows in the truth table where the final result is 1 (True).
  2. For each of these rows, create a conjunct (an AND clause).
  3. Within each conjunct, if a variable’s value in that row is 1, use the variable directly (e.g., \(A\)).
  4. If a variable’s value is 0, use its negation (e.g., \(¬A\)).
  5. Connect all the resulting conjuncts with the disjunction (\(∨\)) operator.
1.4.2 Conjunctive Normal Form (CNF)

A formula is in Conjunctive Normal Form (CNF) if it is a conjunction (ANDs) of disjuncts (ORs of literals).

  • Structure: \((A \lor \neg B) \land (C \lor D) \land (\neg E)\)
  • Intuition: Think of CNF as a set of rules or constraints, all of which must be satisfied for the formula to be true. The formula is made false if any single clause is false.
Algorithm to Find CNF from a Truth Table:
  1. Identify all rows in the truth table where the final result is 0 (False).
  2. For each of these rows, create a disjunct (an OR clause).
  3. Within each disjunct, if a variable’s value in that row is 0, use the variable directly (e.g., \(A\)).
  4. If a variable’s value is 1, use its negation (e.g., \(¬A\)). (This is the opposite of the DNF rule).
  5. Connect all the resulting disjuncts with the conjunction (\(∧\)) operator.

2. Definitions

  • Proposition: A declarative statement that is unambiguously either true or false.
  • Truth Table: A table that displays the truth values of a logical formula for all possible combinations of truth values of its component variables.
  • Literal: A propositional variable (e.g., \(A\)) or its negation (e.g., \(¬A\)).
  • Conjunct (Minterm): A conjunction (AND) of one or more literals. For example, \(A ∧ ¬B ∧ C\).
  • Disjunct (Maxterm): A disjunction (OR) of one or more literals. For example, \(A ∨ ¬B ∨ C\).
  • Disjunctive Normal Form (DNF): A logical formula written as a disjunction of conjuncts. It is an OR of ANDs.
  • Conjunctive Normal Form (CNF): A logical formula written as a conjunction of disjuncts. It is an AND of ORs.

3. Formulas

  • Implication Equivalence: \(P → Q \equiv ¬P ∨ Q\)
  • Biconditional Equivalence: \(P ↔ Q \equiv (P → Q) ∧ (Q → P) \equiv (¬P ∨ Q) ∧ (P ∨ ¬Q)\)
  • General Formula for DNF: \[f = \bigvee_{f(\sigma_1, ..., \sigma_n)=1} (x_1^{\sigma_1} \land ... \land x_n^{\sigma_n})\]
  • General Formula for CNF: \[f = \bigwedge_{f(\sigma_1, ..., \sigma_n)=0} (x_1^{\overline{\sigma_1}} \lor ... \lor x_n^{\overline{\sigma_n}})\]

4. Examples

4.1. Construct a Truth Table (Lab 1, Task 1)

Construct the full truth table for the expression \(¬a ∨ b\).

Click to see the solution
  1. Set up columns: We need columns for the variables \(a\) and \(b\), the negation \(¬a\), and the final expression \(¬a ∨ b\).
  2. List input combinations: For two variables, there are \(2^2=4\) combinations.
  3. Evaluate \(¬a\): This is the opposite of the value of \(a\).
  4. Evaluate \(¬a ∨ b\): This is true if \(¬a\) is true or \(b\) is true.
a b ¬a ¬a ∨ b
0 0 1 1
0 1 1 1
1 0 0 0
1 1 0 1
Answer: The final truth values for the expression are (1, 1, 0, 1).
4.2. Obtain DNF from a Truth Table (Lab 1, Task 1)

Obtain the Disjunctive Normal Form (DNF) from the truth table represented by the vector \(T(a, b) = (0110)\).

Click to see the solution
  1. Construct the truth table: The vector T(a, b) = (0110) defines the output column for all combinations of inputs a and b.
a b f(a,b)
0 0 0
0 1 1
1 0 1
1 1 0
  1. Identify true rows: The function has a value of 1 for the input combinations (0,1) and (1,0).
  2. Form minterms: For each row where the function is true, create a conjunction (AND term). If a variable is 0, it is negated; if it is 1, it is used as is.
    • Row 2 (a=0, b=1): \(¬a ∧ b\)
    • Row 3 (a=1, b=0): \(a ∧ ¬b\)
  3. Combine minterms: The DNF is the disjunction (OR) of these minterms.
Answer: The DNF is \((¬a ∧ b) ∨ (a ∧ ¬b)\).
4.3. Obtain CNF from a Truth Table (Lab 1, Task 2)

Obtain the Conjunctive Normal Form (CNF) from the truth table represented by the vector \(T(a, b) = (1000)\).

Click to see the solution
  1. Construct the truth table: The vector T(a, b) = (1000) defines the output column.
a b f(a,b)
0 0 1
0 1 0
1 0 0
1 1 0
  1. Identify false rows: The function has a value of 0 for the input combinations (0,1), (1,0), and (1,1).
  2. Form maxterms: For each row where the function is false, create a disjunction (OR term). If a variable is 0, it is used as is; if it is 1, it is negated.
    • Row 2 (a=0, b=1): \(a ∨ ¬b\)
    • Row 3 (a=1, b=0): \(¬a ∨ b\)
    • Row 4 (a=1, b=1): \(¬a ∨ ¬b\)
  3. Combine maxterms: The CNF is the conjunction (AND) of these maxterms.
Answer: The CNF is \((a ∨ ¬b) ∧ (¬a ∨ b) ∧ (¬a ∨ ¬b)\).
4.4. Obtain DNF and CNF from a Truth Table (Lab 1, Task a)

Obtain both DNF and CNF from the truth table \(T(x, y) = (1001)\).

Click to see the solution
  1. Construct the truth table:
x y f(x,y)
0 0 1
0 1 0
1 0 0
1 1 1
  1. For DNF (Disjunctive Normal Form):
    • Identify true rows: (0,0) and (1,1).
    • Form minterms: (¬x ∧ ¬y) and (x ∧ y).
    • Combine minterms with OR: \((¬x ∧ ¬y) ∨ (x ∧ y)\).
  2. For CNF (Conjunctive Normal Form):
    • Identify false rows: (0,1) and (1,0).
    • Form maxterms: (x ∨ ¬y) and (¬x ∨ y).
    • Combine maxterms with AND: \((x ∨ ¬y) ∧ (¬x ∨ y)\).

Answer:

  • DNF: \(((¬x ∧ ¬y) ∨ (x ∧ y)\)
  • CNF: \((x ∨ ¬y) ∧ (¬x ∨ y)\)
4.5. Obtain DNF and CNF from a Truth Table (Lab 1, Task b)

Obtain both DNF and CNF from the truth table \(T(x_1, x_2) = (0100)\).

Click to see the solution
  1. Construct the truth table:
x₁ x₂ f(x₁,x₂)
0 0 0
0 1 1
1 0 0
1 1 0
  1. For DNF (Disjunctive Normal Form):
    • Identify true row: (0,1).
    • Form minterm: \(¬x_1 ∧ x_2\).
    • The DNF is just this single minterm.
  2. For CNF (Conjunctive Normal Form):
    • Identify false rows: (0,0), (1,0), and (1,1).
    • Form maxterms: (\(x_1 ∨ x_2\)), (\(¬x_1 ∨ x_2\)), and (\(¬x_1 ∨ ¬x_2\)).
    • Combine maxterms with AND: (\(x_1 ∨ x_2) ∧ (¬x_1 ∨ x_2) ∧ (¬x_1 ∨ ¬x_2)\).

Answer:

  • DNF: \(¬x_1 ∧ x_2\)
  • CNF: \((x_1 ∨ x_2) ∧ (¬x_1 ∨ x_2) ∧ (¬x_1 ∨ ¬x_2)\)
4.6. Obtain DNF and CNF from a Truth Table (Lab 1, Task c)

Obtain both DNF and CNF from the truth table \(T(a, b, c) = (01010110)\).

Click to see the solution
  1. Construct the truth table:
a b c f(a,b,c)
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0
  1. For DNF (Disjunctive Normal Form):
    • Identify true rows: (0,0,1), (0,1,1), (1,0,1), (1,1,0).
    • Form minterms: (\(¬a ∧ ¬b ∧ c\)), (\(¬a ∧ b ∧ c\)), (\(a ∧ ¬b ∧ c\)), (\(a ∧ b ∧ ¬c\)).
    • Combine with OR: \((¬a ∧ ¬b ∧ c) ∨ (¬a ∧ b ∧ c) ∨ (a ∧ ¬b ∧ c) ∨ (a ∧ b ∧ ¬c)\).
  2. For CNF (Conjunctive Normal Form):
    • Identify false rows: (0,0,0), (0,1,0), (1,0,0), (1,1,1).
    • Form maxterms: (\(a ∨ b ∨ c\)), (\(a ∨ ¬b ∨ c\)), (\(¬a ∨ b ∨ c\)), (\(¬a ∨ ¬b ∨ ¬c\)).
    • Combine with AND: \((a ∨ b ∨ c) ∧ (a ∨ ¬b ∨ c) ∧ (¬a ∨ b ∨ c) ∧ (¬a ∨ ¬b ∨ ¬c)\).

Answer:

  • DNF: \((¬a ∧ ¬b ∧ c) ∨ (¬a ∧ b ∧ c) ∨ (a ∧ ¬b ∧ c) ∨ (a ∧ b ∧ ¬c)\)
  • CNF: \((a ∨ b ∨ c) ∧ (a ∨ ¬b ∨ c) ∧ (¬a ∨ b ∨ c) ∧ (¬a ∨ ¬b ∨ ¬c)\)
4.7. Obtain DNF and CNF from a Truth Table (Lab 1, Task d)

Obtain both DNF and CNF from the truth table \(T(y_1, y_2, y_3) = (10000111)\).

Click to see the solution
  1. Construct the truth table:
y₁ y₂ y₃ f(y₁,y₂,y₃)
0 0 0 1
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
  1. For DNF (Disjunctive Normal Form):
    • Identify true rows: (0,0,0), (1,0,1), (1,1,0), (1,1,1).
    • Form minterms: (\(¬y_1 ∧ ¬y_2 ∧ ¬y_3\)), (\(y_1 ∧ ¬y_2 ∧ y_3\)), (\(y_1 ∧ y_2 ∧ ¬y_3\)), (\(y_1 ∧ y_2 ∧ y_3\)).
    • Combine with OR: \((¬y_1 ∧ ¬y_2 ∧ ¬y_3) ∨ (y_1 ∧ ¬y_2 ∧ y_3) ∨ (y_1 ∧ y_2 ∧ ¬y_3) ∨ (y_1 ∧ y_2 ∧ y_3)\).
  2. For CNF (Conjunctive Normal Form):
    • Identify false rows: (0,0,1), (0,1,0), (0,1,1), (1,0,0).
    • Form maxterms: (\(y_1 ∨ y_2 ∨ ¬y_3\)), (\(y_1 ∨ ¬y_2 ∨ y_3\)), (\(y_1 ∨ ¬y_2 ∨ ¬y_3\)), (\(¬y_1 ∨ y_2 ∨ y_3\)).
    • Combine with AND: \((y_1 ∨ y_2 ∨ ¬y_3) ∧ (y_1 ∨ ¬y_2 ∨ y_3) ∧ (y_1 ∨ ¬y_2 ∨ ¬y_3) ∧ (¬y_1 ∨ y_2 ∨ y_3)\).

Answer:

  • DNF: \((¬y_1 ∧ ¬y_2 ∧ ¬y_3) ∨ (y_1 ∧ ¬y_2 ∧ y_3) ∨ (y_1 ∧ y_2 ∧ ¬y_3) ∨ (y_1 ∧ y_2 ∧ y_3)\)
  • CNF: \((y_1 ∨ y_2 ∨ ¬y_3) ∧ (y_1 ∨ ¬y_2 ∨ y_3) ∧ (y_1 ∨ ¬y_2 ∨ ¬y_3) ∧ (¬y_1 ∨ y_2 ∨ y_3)\)
4.8. Construct a Truth Table (Lab 1, Task a)

Construct the full truth table for the expression \((p ∧ q) ∨ ¬q\).

Click to see the solution
  1. Set up columns: We need columns for \(p, q\), the intermediate expressions \(p ∧ q\) and \(¬q\), and the final expression.
  2. List input combinations: There are four combinations for two variables.
  3. Evaluate \(p ∧ q\): This is true only when both \(p\) and \(q\) are true.
  4. Evaluate \(¬q\): This is the opposite of the value of \(q\).
  5. Evaluate the final disjunction (∨): The result is true if either \((p ∧ q)\) or \(¬q\) is true.
p q p ∧ q ¬q (p ∧ q) ∨ ¬q
0 0 0 1 1
0 1 0 0 0
1 0 1 1 1
1 1 1 0 1
Answer: The final truth values for the expression are (1, 0, 1, 1).
4.9. Construct a Truth Table (Lab 1, Task b)

Construct the full truth table for the expression \((A ∧ B) → C\).

Click to see the solution
  1. Set up columns: We need columns for variables \(A, B, C\), the intermediate expression \(A ∧ B\), and the final expression.
  2. List input combinations: For three variables, there are \(2^3=8\) combinations.
  3. Evaluate \(A ∧ B\): This is true only when both \(A\) and \(B\) are true.
  4. Evaluate the final implication (→): The result is false only when the left side (\(A ∧ B\)) is true and the right side (\(C\)) is false.
A B C A ∧ B (A ∧ B) → C
0 0 0 0 1
0 0 1 0 1
0 1 0 0 1
0 1 1 0 1
1 0 0 0 1
1 0 1 0 1
1 1 0 1 0
1 1 1 1 1
Answer: The final truth values for the expression are (1, 1, 1, 1, 1, 1, 0, 1).
4.10. Construct a Truth Table (Lab 1, Task c)

Construct the full truth table for the expression \((x ∨ ¬y) → ¬z\).

Click to see the solution
  1. Set up columns: We need columns for \(x, y, z\) and the intermediate expressions \(¬y, ¬z, (x ∨ ¬y)\), and the final expression.
  2. List input combinations: There are 8 combinations for three variables.
  3. Evaluate negations: Fill in the columns for \(¬y\) and \(¬z\).
  4. Evaluate \(x ∨ ¬y\): This is true if \(x\) is true or \(¬y\) is true.
  5. Evaluate the final implication (→): The result is false only when \((x ∨ ¬y)\) is true and \(¬z\) is false.
x y z ¬y ¬z x ∨ ¬y (x ∨ ¬y) → ¬z
0 0 0 1 1 1 1
0 0 1 1 0 1 0
0 1 0 0 1 0 1
0 1 1 0 0 0 1
1 0 0 1 1 1 1
1 0 1 1 0 1 0
1 1 0 0 1 1 1
1 1 1 0 0 1 0
Answer: The final truth values for the expression are (1, 0, 1, 1, 1, 0, 1, 0).
4.11. Construct a Truth Table (Lab 1, Task d)

Construct the full truth table for the expression \((φ ↔ ψ) → ¬(ψ → γ)\).

Click to see the solution
  1. Set up columns: We need columns for \(φ, ψ, γ\) and intermediate expressions \(φ ↔ ψ, ψ → γ, ¬(ψ → γ)\), and the final expression.
  2. List input combinations: There are 8 combinations for three variables.
  3. Evaluate \(φ ↔ ψ\): This is true when \(φ\) and \(ψ\) have the same value.
  4. Evaluate \(ψ → γ\): This is false only when \(ψ\) is true and \(γ\) is false.
  5. Evaluate \(¬(ψ → γ)\): This is the opposite of the previous column.
  6. Evaluate the final implication (→): This is false only when \((φ ↔ ψ)\) is true and \(¬(ψ → γ)\) is false.
φ ψ γ φ ↔︎ ψ ψ → γ ¬(ψ → γ) (φ ↔︎ ψ) → ¬(ψ → γ)
0 0 0 1 1 0 0
0 0 1 1 1 0 0
0 1 0 0 0 1 1
0 1 1 0 1 0 1
1 0 0 0 1 0 1
1 0 1 0 1 0 1
1 1 0 1 0 1 1
1 1 1 1 1 0 0
Answer: The final truth values for the expression are (0, 0, 1, 1, 1, 1, 1, 0).
4.12. Construct a Truth Table (Lab 1, Task e)

Construct the full truth table for the expression \((x_1 ∧ (x_2 → y)) → (x_1 ∨ ¬y)\).

Click to see the solution
  1. Set up columns: We need columns for \(x_1, x_2, y\) and the intermediate expressions \(x_2 → y\), \(x_1 ∧ (x_2 → y)\), \(¬y\), \(x_1 ∨ ¬y\), and the final expression.
  2. List input combinations: There are 8 combinations for three variables.
  3. Evaluate \(x_2 → y\): This is false only when \(x_2\) is true and \(y\) is false.
  4. Evaluate left side \(x_1 ∧ (x_2 → y)\): This is true only when \(x_1\) and \((x_2 → y)\) are both true.
  5. Evaluate \(¬y\): This is the opposite of \(y\).
  6. Evaluate right side \(x_1 ∨ ¬y\): This is true if either \(x_1\) or \(¬y\) is true.
  7. Evaluate final implication (→): This is false only when the left side is true and the right side is false.
x₁ x₂ y x₂ → y x₁ ∧ (x₂ → y) ¬y x₁ ∨ ¬y (x₁ ∧ (x₂ → y)) → (x₁ ∨ ¬y)
0 0 0 1 0 1 1 1
0 0 1 1 0 0 0 1
0 1 0 0 0 1 1 1
0 1 1 1 0 0 0 1
1 0 0 1 1 1 1 1
1 0 1 1 1 0 1 1
1 1 0 0 0 1 1 1
1 1 1 1 1 0 1 1
Answer: The final truth values for the expression are (1, 1, 1, 1, 1, 1, 1, 1). This expression is a tautology.
4.13. Construct a Truth Table (Tutorial 1, Task 1)

Construct the full truth table for the expression \(¬a ∨ b\).

Click to see the solution
  1. Set up columns: We need columns for the variables \(a\) and \(b\), the negation \(¬a\), and the final expression \(¬a ∨ b\).
  2. List input combinations: For two variables, there are \(2^2=4\) combinations of truth values.
  3. Evaluate \(¬a\): This column will have the opposite truth values of column \(a\).
  4. Evaluate \(¬a ∨ b\): The disjunction is true if at least one of the operands (\(¬a\) or \(b\)) is true.
a b ¬a ¬a ∨ b
0 0 1 1
0 1 1 1
1 0 0 0
1 1 0 1
Answer: The final truth values for the expression are (1, 1, 0, 1).
4.14. Construct a Truth Table (Tutorial 1, Task 2)

Construct the full truth table for the expression \((¬a ∨ b) → b\).

Click to see the solution
  1. Set up columns: We need columns for the variables \(a\) and \(b\), the intermediate expressions \(¬a\) and \(¬a ∨ b\), and the final expression \((¬a ∨ b) → b\).
  2. List input combinations: For two variables, there are four possible combinations of truth values.
  3. Evaluate \(¬a\): Find the opposite truth value for \(a\).
  4. Evaluate \(¬a ∨ b\): This is true if either \(¬a\) or \(b\) is true.
  5. Evaluate the final implication: The expression \(X → Y\) is false only when \(X\) is true and \(Y\) is false.
a b ¬a ¬a ∨ b (¬a ∨ b) → b
0 0 1 1 0
0 1 1 1 1
1 0 0 0 1
1 1 0 1 1
Answer: The final truth values for the expression are (0, 1, 1, 1).
4.15. Obtain DNF from a Truth Table (Tutorial 1, Task 1)

Obtain the Disjunctive Normal Form (DNF) from the truth table represented by the vector \(T(a, b) = (1110)\).

Click to see the solution
  1. Construct the truth table: The vector T(a, b) = (1110) defines the output column for all combinations of inputs a and b.
a b f(a,b)
0 0 1
0 1 1
1 0 1
1 1 0
  1. Identify true rows: The function is true (value 1) for the input combinations (0,0), (0,1), and (1,0).
  2. Form minterms: For each true row, create a conjunction (AND term). If a variable is 0, negate it. If it is 1, use it as is.
    • Row 1 (a=0, b=0): \(¬a ∧ ¬b\)
    • Row 2 (a=0, b=1): \(¬a ∧ b\)
    • Row 3 (a=1, b=0): \(a ∧ ¬b\)
  3. Combine minterms: Combine the minterms with disjunction (OR).
Answer: The DNF is \((¬a ∧ ¬b) ∨ (¬a ∧ b) ∨ (a ∧ ¬b)\).
4.16. Obtain CNF from a Truth Table (Tutorial 1, Task 2)

Obtain the Conjunctive Normal Form (CNF) from the truth table represented by the vector \(T(a, b) = (1000)\).

Click to see the solution
  1. Construct the truth table: The vector T(a, b) = (1000) defines the output column.
a b f(a,b)
0 0 1
0 1 0
1 0 0
1 1 0
  1. Identify false rows: The function is false (value 0) for the input combinations (0,1), (1,0), and (1,1).
  2. Form maxterms: For each false row, create a disjunction (OR term). If a variable is 0, use it as is. If it is 1, negate it.
    • Row 2 (a=0, b=1): \(a ∨ ¬b\)
    • Row 3 (a=1, b=0): \(¬a ∨ b\)
    • Row 4 (a=1, b=1): \(¬a ∨ ¬b\)
  3. Combine maxterms: Combine the maxterms with conjunction (AND).
Answer: The CNF is \((a ∨ ¬b) ∧ (¬a ∨ b) ∧ (¬a ∨ ¬b)\).
4.17. Construct a Truth Table (Tutorial 1, Task 3)

Construct the full truth table for the expression \((¬a → b) ↔ (¬b ∧ c)\).

Click to see the solution
  1. Set up columns: We need columns for variables \(a, b, c\), intermediate expressions \(¬a, ¬b, (¬a → b), (¬b ∧ c)\), and the final expression.
  2. List input combinations: For three variables, there are \(2^3=8\) combinations.
  3. Evaluate negations: Fill in the columns for \(¬a\) and \(¬b\).
  4. Evaluate left side (\(¬a → b\)): This is false only when \(¬a\) is true and \(b\) is false.
  5. Evaluate right side (\(¬b ∧ c\)): This is true only when both \(¬b\) and \(c\) are true.
  6. Evaluate the final biconditional (\(↔\)): The result is true when both sides have the same truth value.
a b c ¬a ¬b ¬a → b ¬b ∧ c (¬a → b) ↔︎ (¬b ∧ c)
0 0 0 1 1 0 0 1
0 0 1 1 1 0 1 0
0 1 0 1 0 1 0 0
0 1 1 1 0 1 0 0
1 0 0 0 1 1 0 0
1 0 1 0 1 1 1 1
1 1 0 0 0 1 0 0
1 1 1 0 0 1 0 0
Answer: The final truth values for the expression are (1, 0, 0, 0, 0, 1, 0, 0).